"""""""""""""""""""""""""""""""""""""""""""""
This module represents my attempt to build
a dictionary using a trie structure.
"""""""""""""""""""""""""""""""""""""""""""""

#
# This class represents a node in the trie-structured dictionary
#
class TrieNode(object):

    def __init__(self, val):
        self.val = val          # the character at this node
        self.branches = []      # the branches of this node
        self.is_word = False    # is the prefix at this node a valid word?
        self.meaning = ''       # the meaning of the word

    # Add a branch to this node
    def add_branch(self, node):
        self.branches.append(node)

    # Search this node's branches to find
    # a branch with the specified character.
    def get_branch(self, ch):
        ch = ch.upper()
        for node in self.branches:
            if node.val == ch:
                return node
        return None


#
# This class represents the trie-structured dictionary
#
class TrieDictionary(object):

    def __init__(self):
        self.ROOT_NODE = TrieNode('')   # The root of the trie.

    # Add a word-meaning pair to the dictionary
    def add_word_and_meaning(self, word, meaning):
        curr_node = self.ROOT_NODE

        for ch in word:
            ch_node = curr_node.get_branch(ch)

            if ch_node is None:
                ch_node = TrieNode(ch)
                curr_node.add_branch(ch_node)

            curr_node = ch_node

        curr_node.is_word = True        # a word ends at this node
        curr_node.meaning = meaning     # set its meaning


    # Get words that start with the given prefix
    def get_words_with_prefix(self, prefix):
        prefix = prefix.upper()
        wordlist = []

        last_node = self.navigate_to_last_node(prefix)
        if last_node is None:
            return None
        else:
            return self.get_words_from_node(last_node, prefix, wordlist)


    # Start from this node and get valid words
    def get_words_from_node(self, node, prefix, wordlist):
        if node.is_word:
            wordlist.append(prefix)

        for branch in node.branches:
            new_prefix = str(prefix) + str(branch.val)
            self.get_words_from_node(branch, new_prefix, wordlist)

        return wordlist


    # Is this word valid?
    def is_correct_word(self, word):
        last_node = self.navigate_to_last_node(word)

        if last_node is None:
            return False
        else:
            return last_node.is_word


    def get_meaning(self, word):
        last_node = self.navigate_to_last_node(word)

        if last_node is None:
            return None
        else:
            return last_node.meaning


    # Get to the last node of the word
    def navigate_to_last_node(self, prefix):
        curr_node = self.ROOT_NODE

        for ch in prefix:
            ch_node = curr_node.get_branch(ch)
            if ch_node is None:
                return None
            else:
                curr_node = ch_node

        return curr_node



#
# This class represents a Suffix trie
#
class SuffixTrie(object):

    def __init__(self):
        self.trie = TrieDictionary()

    def add_word(self, word):
        reversed_word = word[::-1]
        self.trie.add_word_and_meaning(reversed_word, None)

    def get_words_with_suffix(self, suffix):
        reversed_suffix = suffix[::-1]
        reversed_list = self.trie.get_words_with_prefix(reversed_suffix)

        good_list = []
        for reversed_word in reversed_list:
            word = reversed_word[::-1]
            good_list.append(word)

        return good_list



